import java.util.*;

public class FindWords {

    public static void main(String[] args) {
        FindWords findWords = new FindWords();
        char[][] board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        String[] words = {"oath","pea","eat","rain"};
        System.out.println(findWords.findWords(board, words));
    }

    Trie trie;
    boolean[][] flag;
    StringBuilder stringBuilder;
    char[][] board;
    int m;
    int n;
    int[][] temp = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    Set<String> ans = new HashSet<>();

    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        this.board = board;
        flag = new boolean[m][n];
        stringBuilder = new StringBuilder();
        trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                stringBuilder.append(board[i][j]);
                dfs(i, j);
                stringBuilder = new StringBuilder();
            }
        }
        return new ArrayList<>(ans);
    }

    public void dfs(int i, int j) {
        int search = trie.search(stringBuilder.toString());
        if (search == 0) {
            return;
        } else if (search == 2) {
            ans.add(stringBuilder.toString());
        }

        flag[i][j] = true;
        for (int[] ints : temp) {
            int x = i + ints[0];
            int y = j + ints[1];
            if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y]) {
                stringBuilder.append(board[x][y]);
                dfs(x, y);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
        flag[i][j] = false;
    }

    private class Trie {
        Trie[] next;
        int p;

        public Trie() {
            next = new Trie[26];
        }

        public void insert(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = new Trie();
                node = node.next[c - 'a'];
            }
            node.p++;
        }

        //判断是否是前缀或者是单词，返回0代表啥也不是，1代表是前缀，2代表是单词
        public int search(String s) {
            if (s == "") return 1;
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (node.next[c - 'a'] == null) return 0;
                node = node.next[c - 'a'];
            }
            return node.p > 0 ? 2 : 1;
        }
    }
}
